#pragma once
namespace bit_map {
	template<size_t N>
	class bitmap {
	public:
		bitmap() {
			_bits.resize(N / 8+1, 0);
		}
		//设置某一位为1
		void set(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;
			_bits[i] |= (1 << j);

		}
		//重新设定其值
		//将该为设置为0，其他位不变
		void reset(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;

			_bits[i] &= (~(1 << j));

		}
		//测试
		bool test(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;

			return _bits[i] & (1 << j);
		}

	private:
		vector<char> _bits;
	};


	//双位图甚至是多位图，可以用两个位图去表示4个状态
	//这里是只统计出现一次的次数
	template<size_t N>
	class twobitmap {
	public:
		//设置某一位为1
		void set(size_t x)
		{		
			if (!_bits1.test(x) && !_bits2.test(x)) //00 --> 01
			{
				_bits2.set(x);
			}
			else if (!_bits1.test(x) && _bits2.test(x))  //01 ---10
			{
				_bits1.set(x);
				_bits2.reset(x);
			}
		}
		//测试
		bool test(size_t x)
		{
			return !_bits1.test(x) && _bits2.test(x);
		}
	private:
		bitmap<N> _bits1;   //内置类型不处理，自定义类型调用自己的默认构造
		bitmap<N> _bits2;
	};
	void Testbitmap()
	{
		bitmap<100> bp;
		bp.set(99);
		bp.set(91);
		bp.set(90);
		bp.set(92);
		bp.set(94);
		bp.set(22);
		bp.set(39);
		cout << bp.test(99) << endl;
		cout << bp.test(91) << endl;
		cout << bp.test(0) << endl;
		cout << bp.test(22) << endl;
	}
	void Testtwobitmap()
	{
		twobitmap<20> tbp;
		tbp.set(11);
		tbp.set(12);
		tbp.set(13);
		tbp.set(14);
		tbp.set(11);
		tbp.set(12);
		tbp.set(13);
		tbp.set(1);
		cout << tbp.test(11) << endl;
		cout << tbp.test(12) << endl;
		cout << tbp.test(14) << endl;
	}
}